package com.yuxi.al.sort;

/**
 * Created by yuxi on 17/2/5.
 */
public class QuickSort {
    public static void main(String[] args) {
        //快速排序
        int[] arr = {2, 3, 1, 33, 2, 4, 56, 42, 3, 21, 6, 7, 5};
        quickSort(arr, 0, arr.length - 1);
        //排序后
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left > right) return;
        int partion = getPartion(arr, left, right);
        quickSort(arr, left, partion-1 );
        quickSort(arr, partion+1 , right);
    }

    private static int getPartion(int[] arr, int left, int right) {
        int tmp = arr[left];
        while (left < right) {
            while (left < right && arr[right] > tmp)
                right--;
            arr[left] = arr[right];

            while (left < right && arr[left] <= tmp)
                left++;
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }
}
